/********************************************************************************************************************************
 * 单链表
 * 
 * 线性表的链式存储
 * 
 ********************************************************************************************************************************/
#include <cstdlib>
#include <cstdio>

/**
 * 单链表中结点类型的描述
 * */
typedef int ElemType;                        //定义元素的类型

typedef struct LNode{                       //定义单链表的结点类型
    ElemType data;                          //数据域
    struct LNode *next;                     //指针域
}LNode,*LinkList;

/********************************************************************************************************************************
 * 
 * 不带头结点
 * 
 * */

/**
 * 初始化一个空的单链表
 * */

bool InitList(LinkList &L){
    L = NULL;                                   //空表，暂时没有任何结点
    return true;
}

/**
 * 判断单链表是否为空
 * */
bool Empty(LinkList L){
    return (L == NULL);
}

/**
 * 返回链表L的第i个元素
 * */
LinkList GetElem(LinkList &L, int i){

}
/**
 * 插入结点操作
 * 
 * 插入到单链表的第i个位置
 * */
bool ListInsert_Right(LinkList &L,int i,ElemType x){
    if(i < 1)                                   //检查插入位置下限的合法性
        return false;
        
    /* 插入第1个结点的操作与其他结点操作不同 */
    if(i == 1){
        LNode *s = (LNode *)malloc(sizeof(LNode));
        s->data = x;
        s->next = L;
        L = s;                                  //头指针指向新节点

        return true;
    }
    
    LNode *p;                                   //指针p指向当前扫描到的结点
    int j = 0;                                  //当前p指向的是第几个结点
    p =  L;                                     //L指向头结点，投机诶单是第0个结点
    while(p != NULL && j < i - 1){              //循环找到第i - 1 个结点; 当 i 的值超出范围即p == NULL 时
        p = p->next;
        j++;
    }    
    if(p == NULL)                               //处理上限问题：当 i 的值超出上限时，p == NULL,
        return false;              

    LNode *s = (LNode *)malloc(sizeof(LNode));  //创建新结点
    s->data = x;
    LNode *p = GetElem(L, i - 1);               //查找插入位置的前驱结点
    s->next = p->next;                          //设置后继结点
    p->next = s;                                //设置前驱结点

    return true;
}



/********************************************************************************************************************************
 * 
 * 测试程序
 * 
 * */
void test(){
    LinkList L;         //申明一个指向单链表的指针

    InitList(L);        //初始化
}